/*
 * @Author: _LJP 2634716776@qq.com
 * @Date: 2024-01-04 15:00:57
 * @LastEditors: _LJP 2634716776@qq.com
 * @LastEditTime: 2024-01-17 17:41:36
 * @FilePath: /my_-linux/Pro24/Tree/RBT/RBTree/RBTree.hpp
 * @Description: 这是默认设置,请设置`customMade`, 打开koroFileHeader查看配置 进行设置: https://github.com/OBKoro1/koro1FileHeader/wiki/%E9%85%8D%E7%BD%AE
 */
#include<iostream>

#include<vector>

enum COLOR{
    //红黑树的颜色控制,采用枚举确保颜色只能是红或黑
    RED,
    BLACK
};

/*

    红黑树是搜索二叉树;
    同时红黑树利用颜色控制二叉树的平衡;
    
    红黑树确保没有一条路径会比其他路径长出二倍;
    不为高度平衡 而为近似平衡;

*/


/* 
    红黑树的规则:
    1.每个节点不是红色就是黑色;
    2.根节点是黑色;
    3.如果一个节点是红色的,则它的两个孩子节点是黑色;
    4.对于每个节点,从该节点到其所有后代节点的简单路径上,均包含相同数目的黑色节点
    5.每个叶子节点都是黑色的(这里的叶子节点指的是空节点NIL)

    为什么满足上面的性质红黑树就能保证:其最长路径中节点个数不会超过最短路径节点个数的两倍?
        最短路径即为全黑路径
        最长路径可以指的是红黑相接的路径
        假设存在N个黑色节点的话(包括NIL空节点),则红黑相间的红色节点个数为N-1,则最终的节点个数为2N-1;

*/
template<class K,class V>
struct RBTreeNode{

    RBTreeNode<K, V> *_left;
    RBTreeNode<K, V> *_right;
    RBTreeNode<K, V> *_parent;
    std::pair<K,V> _kv; 
    COLOR _col;

    RBTreeNode(const std::pair<K,V>& kv)
    :_left(nullptr)
    ,_right(nullptr)
    ,_parent(nullptr)
    ,_kv(kv)
    ,_col(RED)//给定缺省值默认为红色
    {}
    /*
        节点颜色默认值为新增的节点为红色还是黑色的问题
        这是选择违反红黑树规则中规则3和规则4的问题,权衡利弊宁可违反规则3也不违反规则4;
    */
};

template<class K,class V>
class RBTree{
    typedef RBTreeNode<K,V> Node;
public:

    ~RBTree(){
        _Destory(_root);
    }

    void InOrder(){
        _InOrder(_root);
    }

    Node *Find(const K &key){
        Node* cur = _root;
        while(cur){
            if(key>cur->_kv.first){
                cur = cur->_right;
            }
            else if(key<cur->_kv.first){
                cur = cur->_left;
            }
            else{
                return cur;
            }
        }
        return nullptr;
    }

    bool Insert(const std::pair<K,V>& kv){
        if(_root == nullptr){
            _root = new Node(kv);
            _root->_col = BLACK;
            return true;
        }
        
        Node *cur = _root;
        Node *parent = nullptr;

        while(cur){
            if(cur->_kv.first < kv.first){
                parent = cur;
                cur = cur->_right;
            }
            else if(cur->_kv.first > kv.first){
                parent = cur;
                cur = cur->_left;
            }
            else{
                return false;
            }
        }

        cur = new Node(kv);
        if(parent->_kv.first < kv.first){
            parent->_right = cur;
            cur->_parent = parent;
        }
        else{
            parent->_left = cur;
            cur->_parent = parent;
        }

        while(parent && parent->_col == RED){
            //由于默认插入的节点为红色 所以当parent节点存在且为红色时表示需要进行调整
            Node *grandfather = parent->_parent;//根节点必须为黑色 所以说明该节点上还有节点
            if(grandfather->_left == parent){
                Node *uncle = grandfather->_right;
                
                //插入时颜色的变化分三种情况
                if(uncle && uncle->_col == RED){
                    /*
                        uncle存在且为红
                        当uncle存在且为红的时候，说明cur节点为新增节点
                        这时候的处理方式只需要对节点进行变色处理即可
                        将parent节点与uncle节点变黑 uncle节点变红
                    */
                    parent->_col = BLACK;
                    uncle->_col = BLACK;
                    grandfather->_col = RED;

                    cur = grandfather;
                    parent = cur->_parent;
                }

                else{
                     // if(uncle == nullptr || uncle->_col == BLACK)
                     /*
                        另一种情况即为uncle节点不存在或者uncle节点存在且为黑色节点
                            当uncle节点不存在时说明cur节点为新增节点
                            当uncle节点存在但是节点颜色为黑色时说明cur节点不为新增节点
                        而是由情况1变化而来;
                        这两种情况虽然cur节点的状态不同但是真正意义上来说两者在处理方式可以以相同的方式进行处理
                        

                        但是uncle节点不存在或是uncle存在且为黑的情况虽然统一采取同一种方式进行处理
                        但是还将这种处理方式进行两种情况的划分 分别为cur节点处于parent节点的左子树还是右子树
                        通过左子树或者是右子树取决于使用的措施是采用单选操作还是双旋操作
                     */
                    if(cur == parent->_left){
                        RotateR(grandfather);

                        
                            // parent->_col = RED;
                            // grandfather->_col = cur->_col = BLACK;
                        

                        parent->_col = BLACK;
                        grandfather->_col = RED;
                    }
                    else{ // cur == parent->_left
                        RotateL(parent);
                        RotateR(grandfather);
                        
                            // cur->_col = RED;
                            // grandfather->_col = BLACK;
                            // parent->_col = BLACK;
                        
                       cur->_col = BLACK;
                       grandfather->_col = RED;
                    }
                    break;
                }
            }

            else{ 
                // if(grandfather->_right == parent){
                Node *uncle = grandfather->_left;
                if (uncle && uncle->_col == RED){
                    parent->_col = BLACK;
                    uncle->_col = BLACK;
                    grandfather->_col = RED;
                    
                    cur = grandfather;
                    parent = cur->_parent;
                }
                else{
                     // if(uncle == nullptr || uncle->_col == BLACK)
                     if(cur == parent->_right){
                        RotateL(grandfather);

                  
                        grandfather->_col = RED;
                        
                        parent->_col = BLACK;

                     }

                     
                     else{
                         RotateR(parent);
                         RotateL(grandfather);

                        cur->_col = BLACK;
                        grandfather->_col = RED;
                     }
                     break;
                }
            }
        }
        _root->_col = BLACK;

        return true;

    }

    bool IsBalance(){
        if(_root == nullptr){
            return true;
        }

        if(_root && _root->_col == RED){
            //头节点为红色节点说明树的插入或者某次旋转后的颜色变化出现问题
            return false;
        }
        
        std::pair<bool,std::vector<int>> ret ;
        ret.first = true;
        _Check(ret,_root,0);

        if(!ret.first){
            std::cout << "某一路径出现连续红色节点" << std::endl;
        }

        bool to_comp = true;
        size_t _comp = ret.second[0];
        for(auto &it : ret.second){
            if(it != _comp){
                to_comp = false;
                break;
            }

            std::cout << it << std::endl;
        }

        

        return to_comp && ret.first;
    }

    int getHeight()
    {
        return getHeight(_root);
    }

protected:


    void RotateL(Node *parent){


        Node *cur = parent->_right;
        Node *curleft = cur->_left;

        parent->_right = curleft;
        if (curleft)
        {
            curleft->_parent = parent;
        }

        cur->_left = parent;

        Node *ppnode = parent->_parent;

        parent->_parent = cur;

        if (parent == _root)
        {
            _root = cur;
            cur->_parent = nullptr;
        }
        else
        {
            if (ppnode->_left == parent)
            {
                ppnode->_left = cur;
            }
            else
            {
                ppnode->_right = cur;
            }

            cur->_parent = ppnode;
        }
    }

    void RotateR(Node *parent){
        

        Node *cur = parent->_left;
        Node *curright = cur->_right;

        parent->_left = curright;
        if (curright)
            curright->_parent = parent;

        Node *ppnode = parent->_parent;
        cur->_right = parent;
        parent->_parent = cur;

        if (ppnode == nullptr)
        {
            _root = cur;
            cur->_parent = nullptr;
        }
        else
        {
            if (ppnode->_left == parent)
            {
                ppnode->_left = cur;
            }
            else
            {
                ppnode->_right = cur;
            }

            cur->_parent = ppnode;
        }
    }

    void _InOrder(Node *root){
        if(root == nullptr) return ;
        _InOrder(root->_left);
        std::cout << root->_kv.first << " : " << root->_kv.second << " col : " << root->_col << std::endl;
        _InOrder(root->_right);
    }

    void _Check(std::pair<bool,std::vector<int>> &ret,Node *root,size_t blackNum = 0){
        
        if(root == nullptr){
            ret.first = ret.first && true;
            ret.second.push_back(blackNum);
            return;
        }

        if(root->_col == RED && root->_parent->_col == RED){
            ret.first = ret.first && false;
            return ;
        }

        if(root->_col == BLACK){
            blackNum++;
        }

        _Check(ret, root->_left, blackNum);
        _Check(ret, root->_right, blackNum);
    }
    
    int getHeight(Node *root)
    {
        if (root == nullptr)
        {
            return 0;
        }
        int left = getHeight(root->_left);
        int right = getHeight(root->_right);

        return left > right ? left + 1 : right + 1;
    }

    void _Destory(Node* &root){
        if(root == nullptr){
            return ;
        }

        _Destory(root->_left);
        _Destory(root->_right);

        delete root;

        root = nullptr;
    }

private:
    Node* _root = nullptr;

    
};